// 给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

// 字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

// 说明：
// 字母异位词指字母相同，但排列不同的字符串。
// 不考虑答案输出的顺序。




// 示例 1:
// 输入:
// s: "cbaebabacd" p: "abc"
// 输出:
// [0, 6]
// 解释:
// 起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
// 起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。


//  示例 2:
// 输入:
// s: "abab" p: "ab"
// 输出:
// [0, 1, 2]
// 解释:
// 起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
// 起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
// 起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。



/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
    let
        left = 0,
        right = 0,
        valid = 0,
        need = {},
        window = {};
    p.split('').forEach(item => {
        if (need[item] === undefined) {
            need[item] = 1;
            window[item] = 0;
        } else {
            need[item]++;
        }
    });
    let
        nums = [];
    while (right < s.length) {
        let right_curchar = s[right];
        right++;
        if (need[right_curchar] !== undefined) {
            window[right_curchar]++;
            if (need[right_curchar] === window[right_curchar]) {
                valid++;
            }
        }
        if ((right - left) >= p.length) {
            if (valid === [...Object.keys(need)].length) {
                // 符合条件就将起始索引加入数组
                nums.push(left);
            }
            let left_curchar = s[left];
            left++;
            if (need[left_curchar] !== undefined) {
                if (need[left_curchar] === window[left_curchar]) {
                    valid--;
                }
                window[left_curchar]--;
            }
        }
    };
    return nums;
}

